Navneeth Dhamotharan

~/notes/math_208/TCL2-Gaussian Elimination.md
cd ..
~/notes/math_208/Gaussian Elimination.md

Gaussian Elimination

2026-03-28
math208 linalg carr gaussian_elimination

Now that we know what an augmented matrix is and what it looks like, let's go deeper into

Elementary Row Operations

There are 3 main operations that can be performed on matrices

  1. Multiply any row by a non 0 constant.
  2. Add/Subtract a multiple of any row from any other row.
  3. Swap any two rows. Our main goal is to end up with a matrix like this:
(∗∗∗∣∗0∗∗∣∗00∗∣∗)\begin{pmatrix} * & * & * & | & * \\ 0 & * & * & | & * \\ 0 & 0 & * & | & * \end{pmatrix} 
Example 1. Eliminate the below matrix
(10−3∣−231−2∣5221∣4)\begin{pmatrix} 1 & 0 & -3 & | & -2 \\ 3 & 1 & -2 & | & 5 \\ 2 & 2 & 1 & | & 4 \end{pmatrix}

Lets start by performing two operations to eliminate x1x_1 in rows 2 and 3.

  • R2=R2−3×R1R_2 = R_2 - 3 \times R_1
  • R3=R3−2×R1R_3 = R_3 - 2 \times R_1 The resulting matrix you end up with is:
(10−3∣−2017∣11027∣8)\begin{pmatrix} 1 & 0 & -3 & | & -2 \\ 0 & 1 & 7 & | & 11 \\ 0 & 2 & 7 & | & 8 \end{pmatrix}

Now in order to eliminate that x2x_2 in row 3, change R3R_3 to R3−2×R2R_3 - 2 \times R_2

(10−3∣−2017∣1100−7∣−14)\begin{pmatrix} 1 & 0 & -3 & | & -2 \\ 0 & 1 & 7 & | & 11 \\ 0 & 0 & -7 & | & -14 \end{pmatrix}

This form has achieved that initial goal and is called Echelon form or Row Echelon form, and the process to reach here is called Gaussian Elimination.

In fact, we can keep on reducing the matrix as follows. Let's continue by simplifying the R3=−17×R3R_3 = -\frac{1}{7} \times R_3 and you end up with:

(10−3∣−2017∣11001∣2)\begin{pmatrix} 1 & 0 & -3 & | & -2 \\ 0 & 1 & 7 & | & 11 \\ 0 & 0 & 1 & | & 2 \end{pmatrix}

Then, modify R2=R2−7×R3R_2 = R_2 - 7 \times R_3

(10−3∣−2010∣−3001∣2)\begin{pmatrix} 1 & 0 & -3 & | & -2 \\ 0 & 1 & 0 & | & -3 \\ 0 & 0 & 1 & | & 2 \end{pmatrix}

Finally, you modify R1R_1 to R1=R1+3×R3R_1 = R_1 + 3 \times R_3

(100∣4010∣−3001∣2)\begin{pmatrix} 1 & 0 & 0 & | & 4 \\ 0 & 1 & 0 & | & -3 \\ 0 & 0 & 1 & | & 2 \end{pmatrix}

This resulting form is called the Reduced Echelon Form, and the process to get from row echelon form to reduced echelon form is called Gauss-Jordan Elimination.

The final solution set can be written as (x1,x2,x3)=(4,−3,2)(x_1,x_2,x_3) = (4,-3,2)

How to tell if a solution is inconsistent

Example 2. Evaluate if the below system is inconsistent or not
{−3y+6z=2x+4z=12x+y+6z=0\begin{cases} -3y + 6z = 2 \\ x + 4z = 1 \\ 2x + y + 6z = 0 \end{cases}

Let's write this as an adjacency matrix below:

(0−36∣2104∣1216∣0)\begin{pmatrix} 0 & -3 & 6 & | & 2 \\ 1 & 0 & 4 & | & 1 \\ 2 & 1 & 6 & | & 0 \end{pmatrix}

In order to make life easier, lets move R1R_1 and R2R_2 up one and R3R_3 to the bottom so that we have our top diagonal as 1.

(104∣1216∣00−36∣2)\begin{pmatrix} 1 & 0 & 4 & | & 1 \\ 2 & 1 & 6 & | & 0 \\ 0 & -3 & 6 & | & 2 \end{pmatrix}

R2=R2−2×R1R_2 = R_2 - 2 \times R_1

(104∣101−2∣−20−36∣2)\begin{pmatrix} 1 & 0 & 4 & | & 1 \\ 0 & 1 & -2 & | & -2 \\ 0 & -3 & 6 & | & 2 \end{pmatrix}

R3=R3+3×R2R_3 = R_3 + 3 \times R_2

(104∣101−2∣−2000∣−4)\begin{pmatrix} 1 & 0 & 4 & | & 1 \\ 0 & 1 & -2 & | & -2 \\ 0 & 0 & 0 & | & -4 \end{pmatrix}

That last row tells us 0x+0y+0z=−40x + 0y + 0z = -4 which does not make sense.

Inconsistent solutions
If a matrix is reduced and you obtain a row of the form $\begin{pmatrix} 0 & 0 & 0 & ... & 0 & | & a \end{pmatrix}$, when $a \neq 0$, then the system is inconsistent

Echelon Form

Definition: Row Echelon form
A matrix is in row echelon form (staircase form) if: a) All 0 rows are at the bottom. b) The leading non 0 entry of each row (called the pivot), is strictly to the right of the leading non 0 entry of the row above.

Are Echelon forms unique?

No they are not.

(−∗∗∗∗∗∣∗00−∗∗∗∣∗000−∗∗∣∗000000∣0)\begin{pmatrix} - & * & * & * & * & * & | * \\ 0 & 0 & - & * & * & * & | * \\ 0 & 0 & 0 & - & * & * & | * \\ 0 & 0 & 0 & 0 & 0 & 0 & | 0 \\ \end{pmatrix}

Here −- is any non 0 number and ∗* is any number. The variables associated with the pivot columns are called leading variables. The variables associated with the non pivot columns are called free variables.

Recall this example from the previous notes.

{2x1−x2+5x3−x4=−30x3+x4=−6\begin{cases} 2x_1 - x_2 + 5 x_3 - x_4 = -30 \\ x_3 + x_4 = -6 \end{cases}

putting that in adjacency matrix form

(2−15−1∣−300011∣−6)\begin{pmatrix} 2 & -1 & 5 & -1 & | & -30 \\ 0 & 0 & 1 & 1 & | & -6 \end{pmatrix}

In the example above x1x_1 and x3x_3 are leading variables, and x2x_2 and x4x_4 are called free variables.

Definition: Reduced Row Echelon form
A matrix is in reduced row echelon form (staircase form) if: a) It is in row echelon form b) All the pivots are '1's c) each pivot column has all 0s above it 
Example 3. Take the below matrix in row echelon form and convert it to reduced row echelon form.
(1−14−20∣00020−4∣200010∣500000∣0)\begin{pmatrix} 1 & -1 & 4 & -2 & 0 & | & 0 \\ 0 & 0 & 2 & 0 & -4 & | & 2 \\ 0 & 0 & 0 & 1 & 0 & | & 5 \\ 0 & 0 & 0 & 0 & 0 & | & 0 \\ \end{pmatrix}

Lets start with simplifying row 2. R2=12×R2R_2 = \frac{1}{2} \times R_2

(1−14−20∣00010−2∣100010∣500000∣0)\begin{pmatrix} 1 & -1 & 4 & -2 & 0 & | & 0 \\ 0 & 0 & 1 & 0 & -2 & | & 1 \\ 0 & 0 & 0 & 1 & 0 & | & 5 \\ 0 & 0 & 0 & 0 & 0 & | & 0 \\ \end{pmatrix}

R1=R1+2×R3R_1 = R_1 + 2 \times R_3

(1−1400∣100010−2∣100010∣500000∣0)\begin{pmatrix} 1 & -1 & 4 & 0 & 0 & | & 10 \\ 0 & 0 & 1 & 0 & -2 & | & 1 \\ 0 & 0 & 0 & 1 & 0 & | & 5 \\ 0 & 0 & 0 & 0 & 0 & | & 0 \\ \end{pmatrix}

R1=R1−4×R2R_1 = R_1 - 4 \times R_2

(1−1008∣60010−2∣100010∣500000∣0)\begin{pmatrix} 1 & -1 & 0 & 0 & 8 & | & 6 \\ 0 & 0 & 1 & 0 & -2 & | & 1 \\ 0 & 0 & 0 & 1 & 0 & | & 5 \\ 0 & 0 & 0 & 0 & 0 & | & 0 \\ \end{pmatrix}

This is now in reduced row echelon form. The system of equations that this augmented matrix gives is

{x1−x2+8x5=6x3−2x5=1x4=5\begin{cases} x_1 - x_2 + 8x_5 = 6 \\ x_3 - 2x_5 = 1 \\ x_4 = 5 \end{cases}

Here the free variables are x2x_2 and x5x_5 and the leading variables are x1x_1, x3x_3 and x4x_4. In order to arrive at the final solution, you can parameterize the equations as follows.

Let x2x_2 = ss , x5x_5 = tt x1−s+8t=6x_1 - s + 8t = 6 x1=6−8t+sx_1 = 6 -8t + s

x3−2t=1x_3 - 2t = 1 x3=1+2tx_3 = 1 + 2t

The final solution is

x1=6−8t+sx2=sx3=1+2tx4=5x5=t\begin{gathered} x_1 = 6 -8t + s \\ x_2 = s \\ x_3 = 1 + 2t \\ x_4 = 5 \\ x_5 = t \\ \end{gathered} 
Example 4. For what values of a and b does the below system have
a) One solution.
b) Infinitely many solutions.
c) No solutions.
{x+y+2z=42x+3y=a−y+4z=b\begin{cases} x + y + 2z = 4 \\ 2x + 3y = a \\ -y + 4z = b \end{cases}

Lets start off by putting this in an augmented matrix:

(112∣4230∣a0−14∣b)\begin{pmatrix} 1 & 1 & 2 & | & 4 \\ 2 & 3 & 0 & | & a \\ 0 & -1 & 4 & | & b \\ \end{pmatrix}

R2=R2−2×R1R_2 = R_2 - 2 \times R_1

(112∣401−4∣a−80−14∣b)\begin{pmatrix} 1 & 1 & 2 & | & 4 \\ 0 & 1 & -4 & | & a - 8 \\ 0 & -1 & 4 & | & b \\ \end{pmatrix}

R3=R3+R2R_3 = R_3 + R_2

(112∣401−4∣a−8000∣a+b−8)\begin{pmatrix} 1 & 1 & 2 & | & 4 \\ 0 & 1 & -4 & | & a - 8 \\ 0 & 0 & 0 & | & a + b - 8 \\ \end{pmatrix}

The solution is inconsistent if aa and bb are non 0 or if a+b≠8a+b \neq 8.

If a+b=8a+b = 8, The matrix becomes

(112∣401−4∣a−8000∣0)\begin{pmatrix} 1 & 1 & 2 & | & 4 \\ 0 & 1 & -4 & | & a - 8 \\ 0 & 0 & 0 & | & 0 \\ \end{pmatrix}

and x3x_3 becomes a free variable. Therefore there are infinitely many values of x3x_3 , and therefore infinite solutions to aa and bb .

As a result, the system will never have 1 solution.